#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <time.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
// 插入排序算法通过比较和插入来实现排序，其排序流程如下：
// (1)首先对数组的前两个数据进行从小到大的排序。
// (2)接着将第3个数据与排好序的两个数据比较，将第3个数据插入到合适的位置。
// (3)然后，将第4个数据插入到已排好序的前3个数据中。
// (4)不断重复上述过程，直到把最后一个数据插入合适的位置。最后，便完成了对原始数组从 小到大的排序。
void InsertSort(int *a ,int len)
{
    int i,j,t,h;
    for(i=1;i<len;i++){
        t=a[i];
        j=i-1;
        while (j>=0&&t<a[j])
        {
            /* code */
            a[j+1]=a[j];
            j--;
        for(int i=0;i<len;i++)
        {cout<<j<<endl;
        cout<<a[i]<<" ";
        }
        cout<<endl;
        }
        a[j+1]=t;//注意这里如果是从while循环退出来的话，可能j=-1

    }

}
int main()
{   int needSort[]={112,20,150,360,333,563};
    int len=sizeof(needSort)/sizeof(int);
    InsertSort(needSort,len);
    // for(int i=0;i<len;i++)
    // {
    //     cout<<needSort[i]<<" ";
    // }
    return 0;
}

